/*
 * Project: BoboDesignPattern
 * 
 * File Created at 2020年1月29日
 * 
 * Copyright 2012 Greenline.com Corporation Limited.
 * All rights reserved.
 *
 * This software is the confidential and proprietary information of
 * Greenline Company. ("Confidential Information").  You shall not
 * disclose such Confidential Information and shall use it only in
 * accordance with the terms of the license agreement you entered into
 * with Greenline.com.
 */
package test.lesson3.sort;

import java.util.Arrays;

/**
 * @Type MergeSort
 * @Desc
 * @author 52489
 * @date 2020年1月29日
 * @Version V1.0
 */
public class MergeSort {
    public static void main(String[] args) {
        int nums[] = { 9, 7, 8, 3, 2, 1 };
        int a[] = { 9, 7, 8, 3, 2, 1 };
        mergeSortUp2Down(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
        int i = 0;
        System.out.println(a[i++]);
    }

    public static void mergeSortUp2Down(int[] elem, int start, int end) {
        if (elem == null || start >= end) {
            return;
        }

        int mid = (start + end) / 2;

        mergeSortUp2Down(elem, start, mid);
        mergeSortUp2Down(elem, mid + 1, end);

        merge(elem, start, mid, end);
    }

    public static void merge(int[] elem, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (elem[i] < elem[j]) {
                temp[k++] = elem[i++];
            } else {
                temp[k++] = elem[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = elem[i++];
        }

        while (j <= end) {
            temp[k++] = elem[j++];
        }

        for (i = 0; i < k; i++) {
            elem[start + i] = temp[i];
        }
        temp = null;
    }
}
